package com.jzoffer2;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No39
 * @description
 * @date 2021/2/1 下午1:42
 */
public class No39 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        int res= majorityElement(arr);
        System.out.println(res);
    }

    public static int majorityElement(int[] nums) {
        if(nums == null || nums.length < 1){
            return -1;
        }
        int len = nums.length;
        if(len == 1){
            return nums[0];
        }
        int majorityNum = nums[0];
        int count = 1;
        for (int i = 1; i < len; i++) {
            if(majorityNum == nums[i]){
                count++;
            }else {
                count--;
                if(count == 0){
                    majorityNum = nums[i];
                    count = 1;
                }
            }
        }
        // 检验
        count = 0;
        for (int num:nums) {
            if(num == majorityNum){
                count++;
            }
        }
        if(count >= len / 2){
            return majorityNum;
        }
        return -1;
    }

}
